/*
 * Project: Data Mining using SWARM
 * File: BTree.h
 * Author: Ivan Schwarz, Etienne Baali
 * Description: Implementation of BTreeNode class
 */

#include "BTree.h"
#include <iomanip>

/*
 * Constructor for BTreeNode. Level is computed from the size of key vector.
 * If there is no key vector, size is implicitely 0 - root node.
 */
BTreeNode::BTreeNode(vector<int> * oData,vector<int> * tData, vector<vector<vector<Cl_Object>>> * cData) {
	this->level = keyVec.size();
	this->cSwarm = false;
	oDatabase = oData;
	tDatabase = tData;
	cDatabase = cData;

}

/*
 * Constructor for BTreeNode. Level is computed from the size of key vector.
 * If there is no key vector, size is implicitely 0 - root node.
 * Version where databases will be loaded from file later
 */
BTreeNode::BTreeNode() {
	this->level = keyVec.size();
	this->cSwarm = false;

	vector<int> * oData = new vector<int>();
	for(int i = 0; i < OBJ_NUM; i++)
		oData->push_back(i);

	this->oDatabase = oData;
}

/*
 * Constructor for BTreeNode. Level is computed from the size of key vector.
 */
BTreeNode::BTreeNode(vector<int> keyVec) {
	this->keyVec = keyVec;
	this->cSwarm = false;
	this->level = keyVec.size();
}

/*
 * Insert child node to child list. List remains sorted. 
 */
void BTreeNode::addChild(BTreeNode * node)
{
	vector<BTreeNode*>::iterator it;
	vector<int> nodeKey = node->getKeyVec();
	vector<int> childKey;
	if(node!= NULL) {
		if(childList.empty()) {
			childList.push_back(node);
		} else {
			for(int i=0; i<childList.size(); i++) {
				childKey = childList[i]->getKeyVec();
				if(nodeKey[level] == childKey[level]) { // The same element, ignore it.
					return;			
				} else if(nodeKey[level] < childKey[level]) { // We found the place, where to put our child.
					it = childList.begin();
					childList.insert(it+i,node);
					break;
				} else if(i == (childList.size() - 1)) { // Inserted child has the biggest value, put him at the back.
					childList.push_back(node);
				}
			}
		}
	}
}

/*
 * Insert new node to BTree. Key vector is used as a way to precise leaf, then the addChild method
 * is called.
 */
void BTreeNode::insert(BTreeNode * node) 
{
	int treeLevel;
	BTreeNode * NPtr = NULL; // Temporal pointer 
	vector<int> nodeKey = node->getKeyVec();

	//cout << "Insert: Beginning" << endl;
	NPtr = this;
	while(1) { // Searching for the place where to put the node.
		treeLevel = NPtr->getLevel();
		//cout << "tree level:" << treeLevel << endl;;

		if(treeLevel < (nodeKey.size() - 1)) { // we are not deep enough
			//cout << "Going this way: " << nodeKey[treeLevel] << endl;
			for(int i = 0; i < NPtr->getChildList().size(); i++) {
				if(nodeKey[treeLevel] == NPtr->getChildList().at(i)->getKeyVec().at(treeLevel)) {
					NPtr = NPtr->getChildList().at(i);
				}
			}
		} else if(treeLevel == (node->getKeyVec().size() - 1)) { // level of depth is equal to lenght of key
			NPtr->addChild(node); // add child/leaf into childList
			break;
		} else { // Branches are not structured properly (probably nodes between root and inserted node missing)
			cerr << "BTreeNode:Insert error" << endl;
			break;
		}
    }
}

/*
 * Method for finding Closed Swarm. Implementation based on SWARM paper
 * Apriori and Backward prunning used for eliminating useless branches of tree
 * Forward Closure checking used for determining if Swarm is Closed
 */
void BTreeNode::objectGrowth(int mino,int mint) 
{

	BTreeNode * insertedNode = NULL;
	vector<int> insertedKeyVec;
	vector<int> Tmax; // Maximal Timeset for given objectset
	vector<int> Tmax_prunning;
	int back;
	int g;
	bool f_closure, in_cluster, prunned;

	// Building B-Tree in DFS order
	for(int i = 0; i < oDatabase->size()-1;i++) {

		g = i;
		while(1) {

			insertedKeyVec.push_back(g);

			// Compute Tmax of current objectset O
			Tmax.clear();
			for(int t = 0;t < tDatabase->size();t++) {
				for(int c = 0; c < cDatabase->at(t).size();c++) {

					// Are all objects from objectset in this cluster?
					for(int o = 0; o < insertedKeyVec.size();o++) {

						// Is object from objectset in this cluster?
						// Slow! Optimalization needed!!! 
						in_cluster = false;
						for(int k = 0; k < cDatabase->at(t).at(c).size();k++) { 
							if(insertedKeyVec[o] == cDatabase->at(t).at(c).at(k).getId()) {
								in_cluster = true;
								break;
							}
						}
						if(!in_cluster) { // Some object from objectset is not in this cluster
							break;
						}
					}
					if(in_cluster) { // All objects from objectset are in this cluster, add t to Tmax
						Tmax.push_back(t);
						break;
					}
				}
			}

			if(Tmax.size() >= mint) { // Apriori Prunning: Tmax of objectset is bigger than mint

				// Backward Prunning
				prunned = false;
				int a = insertedKeyVec.front(); 
				int range = insertedKeyVec.back() - insertedKeyVec.front();
				for(int j = 1; j < insertedKeyVec.size(); j++) { // Search in objects lesser than last object of objectset
					for(int k = 0; k < range; k++) { // Object cant be a member of objectset
						a++;
						if(a < insertedKeyVec[j]) {
							insertedKeyVec.push_back(a);
							Tmax_prunning.clear();
							for(int t = 0; t < Tmax.size();t++) {
								for(int c = 0; c < cDatabase->at(Tmax[t]).size(); c++) {
									for(int o = 0; o < insertedKeyVec.size();o++) {

										// Is object from objectset in this cluster?
										// Slow! Optimalization needed!!! 
										in_cluster = false;
										for(int l = 0; l < cDatabase->at(Tmax[t]).at(c).size();l++) { 
											if(insertedKeyVec[o] == cDatabase->at(Tmax[t]).at(c).at(l).getId()) {
												in_cluster = true;
												break;
											}
										}
										if(!in_cluster) { // Some object from objectset is not in this cluster
											break;
										}
									}
									if(in_cluster) { // All objects from objectset are in this cluster
										Tmax_prunning.push_back(Tmax[t]);
										break;
									}

								}
							}
							insertedKeyVec.pop_back();
							if(Tmax.size() == Tmax_prunning.size()) {
								prunned = true;
								break;
							}
							a++;
						} else {
							break;
						}
					}
					if(prunned) { // Objectset is already prunned, no need of continuing
						break;
					}
				}

				if(!prunned) { // Objectset passed both prunning rules

					// Forward Closure Checking
					f_closure = true;
					back = insertedKeyVec.back() + 1;
					for(int j = back;j < oDatabase->size();j++) {
						insertedKeyVec.push_back(j);
						
						for(int t = 0;t < Tmax.size();t++) {
							for(int c = 0; c < cDatabase->at(Tmax[t]).size();c++) {

								// Are all objects from objectset in this cluster?
								for(int o = 0; o < insertedKeyVec.size();o++) {
	
									// Is object from objectset in this cluster?
									// Slow! Optimalization needed!!! 
									in_cluster = false;
									for(int k = 0; k < cDatabase->at(Tmax[t]).at(c).size();k++) { 
										if(insertedKeyVec[o] == cDatabase->at(Tmax[t]).at(c).at(k).getId()) {
											in_cluster = true;
											break;
										}
									}
									if(!in_cluster) { // Some object from objectset is not in this cluster
										break;
									}
								}
								if(in_cluster) { // All objects from objectset are in this cluster
									for(int l = 0; l < cDatabase->at(Tmax[t]).at(c).size();l++) { 
										if(j == cDatabase->at(Tmax[t]).at(c).at(l).getId()) {
											f_closure = false;
											break;
										}
									}
								}
								if(!f_closure) { // Didnt pass forward checking, no need to finish cycle
									break;
								}

							}
							if(!f_closure) { // Didnt pass forward checking, no need to finish cycle
								break;
							}
						}

						insertedKeyVec.pop_back();
					}
					if(f_closure && insertedKeyVec.size() >= mino) { // This objectset is a closed swarm, print it
						cout << "Closed Swarm: ";
						for(int j = 0; j < insertedKeyVec.size();j++) {
							cout << insertedKeyVec[j] << ",";
						}
						cout << endl;
						cout << "Tmax: ";
						for(int j = 0; j < Tmax.size();j++) {
							cout << Tmax[j] << ",";
						}
						cout << endl;
					}
					// Closed Swarm or not, We do a node for it either way
					insertedNode = new BTreeNode(insertedKeyVec);
					insert(insertedNode);
				} else { // Prunned by Backward Prunning
					insertedKeyVec.pop_back();
				}
			} else { // Prunned by Apriori Prunning
				insertedKeyVec.pop_back();
			}

			g++;
			while(g >= oDatabase->size()) { // backtrack and create another branch
				back = insertedKeyVec.back();
				insertedKeyVec.pop_back();
				g = back + 1;
			}
			if(insertedKeyVec.empty()) { // backtracked to root, create another subtree starting by next 'object'
				break;
			}
		}

	}
}


/*
 * Method for reading cluster database from file
 * Computing time database from cluster database
 */
void BTreeNode::readClustersFile(char * fileName)
{

	ifstream pFile;
	char buffer[255];
	char* splitedString;
	int i;

	long double timestamp;
	long double latitud;
	long double longitud;
	int userId;

	vector<Cl_Object> Cl;
	vector<vector<Cl_Object>> tSnapshot;
	vector<vector<vector<Cl_Object>>> * clDatabase = new vector<vector<vector<Cl_Object>>>();
	vector<long double> timeVec;
	int iterator = -1;

	pFile.open(fileName);
	if (!pFile.is_open()) perror ("Error opening file");
	else
	{
		
		while(!pFile.eof()){
			pFile.getline(buffer, 255);

			if(buffer[0] == '{' || buffer[0] == '}' || buffer[0] == ' ' || buffer[0] == '\0'){
			
			}else{

				
				splitedString = strtok(buffer, " ");

				timestamp = rndup(atof(splitedString));

				pFile.getline(buffer, 255);
				while(buffer[0] != '}'){
					i=0;
					splitedString = strtok(buffer, " ");
					while (splitedString != NULL)
					{

					if(i == 0)
						latitud = atof(splitedString);
					if(i == 1)
						longitud = atof(splitedString);
					if(i == 2)
						userId = atof(splitedString);
							
					i++;
					//repeat the call until the end
					splitedString = strtok (NULL, " ");
					}

					Cl_Object tmpObj;
					tmpObj.setId(userId);
					tmpObj.setX(latitud);
					tmpObj.setY(longitud);
					Cl.push_back(tmpObj);

					//add to vector object(lat, long, userId)
				pFile.getline(buffer, 255);

				}

				// Add cluster to database
				if(timeVec.empty() || timeVec.back() != timestamp) { // First cluster for this timestamp, make a new vector for them
					timeVec.push_back(timestamp);
					tSnapshot.push_back(Cl);
					clDatabase->push_back(tSnapshot);
					tSnapshot.clear();
					iterator++;
				} else { // There are already clusters with this timestamp, add it to same vector
					clDatabase->at(iterator).push_back(Cl);
				} 

				Cl.clear();

			}

		}
	}
	this->cDatabase = clDatabase;

	// Make database from timestamps, neglate their distance in time
	vector<int> * tData = new vector<int>;
	for(int t = 0; t < clDatabase->size(); t++)
		tData->push_back(t);

	this->tDatabase = tData;
}

/*
 * Method for printing cluster database.
 * Every timestamp is followed by set of clusters of objects
 */
void BTreeNode::printCDatabase()
{
	cout << ">> CLUSTER DATABASE <<" << endl;
	for(int t = 0; t < tDatabase->size(); t++) {
		cout << "Timestamp: " << t << endl;
		for(int c = 0; c < cDatabase->at(t).size();c++) {
			cout << "{";
			for(int o = 0; o < cDatabase->at(t).at(c).size(); o++) {
				cout << cDatabase->at(t).at(c).at(o).getId();
				if(o != (cDatabase->at(t).at(c).size() - 1)) {
					cout << ",";
				}
			}
			cout << "}" << endl;
		}
	}
}



